package leetcode.all;

import datastruct.tree.TreeNode;

public class Solution543 {

    public int diameterOfBinaryTree(TreeNode root) {
        int[] res = heightAndDiam(root);
        return res[1];
    }

    /**
     * 返回node的高度，以node为根节点的树的直径(这里是指直径所在路径的节点个数)
     * @param node
     * @return
     */
    public int[] heightAndDiam(TreeNode node){
        if(node==null) return new int[]{0,0};
        int[] left = heightAndDiam(node.left);
        int[] right = heightAndDiam(node.right);
        int height = 1+Math.max(left[0],right[0]);
        int maxDiam = Math.max(Math.max(left[1],right[1]),left[0]+right[0]+1);
        return new int[]{height,maxDiam};
    }
}
